use std::collections::HashMap;
use std::rc::Rc;

#[derive(Debug, Default)]
struct HaffmanNode {
    value: Option<char>,
    counter: i32,
    left: Option<Rc<HaffmanNode>>,
    right: Option<Rc<HaffmanNode>>
}
impl HaffmanNode {
    fn new(value: Option<char>, counter: i32) -> HaffmanNode {
        HaffmanNode{
            value,
            counter,
            left: None,
            right: None
        }
    }

    fn is_leaf(&self) -> bool {self.left.is_none() && self.right.is_none()}

    fn raise_value(&mut self) {self.counter += 1;}
}

struct HaffmanCoder {
    d: String,
    root: Rc<HaffmanNode>,
    dict: HashMap<char, String>,
    decode_dict: HashMap<String, char>
}

impl HaffmanCoder {
    fn new(d: String) -> HaffmanCoder {
        HaffmanCoder{
            d,
            root: Rc::default(),
            dict: HashMap::new(),
            decode_dict: HashMap::new()
        }
    }
    fn construct(&mut self) {
        let mut state: HashMap<char, i32> = HashMap::new();
        self.d.to_ascii_lowercase().chars().filter(|x| {x.is_lowercase()}).for_each(|x| {
            state.entry(x).and_modify(|counter| { *counter = *counter + 1 }).or_insert(1);
        });
        let mut data: Vec<Rc<HaffmanNode>> = Vec::from_iter(state.iter().map(|x| {Rc::new(HaffmanNode::new(Some(*x.0), *x.1))}));
        while data.len() > 1 {
            data.sort_by_key(|a| a.counter);
            let t = Rc::new(HaffmanNode{
                value: None,
                counter: data[0].counter + data[1].counter,
                left: Some(data[0].clone()),
                right: Some(data[1].clone())
            });
            data.remove(0);
            data[0] = t;
        }
        self.root = data[0].clone();
        let mark = String::new();
        self.pre_traverse(&data[0].clone(), &mark);
    }
    fn pre_traverse(&mut self, root: &Rc<HaffmanNode>, mark: &String){
        if root.left.is_some() {
            let mark_back = mark.clone() + "1";
            self.pre_traverse(&(root.left.as_ref().unwrap()), &mark_back);
        }
        if root.right.is_some() {
            let mark_back = mark.clone() + "0";
            self.pre_traverse(&(root.right.as_ref().unwrap()), &mark_back);
        }
        if root.is_leaf() {
            self.dict.insert(root.value.unwrap(), mark.clone());
            self.decode_dict.insert(mark.clone(), root.value.unwrap());
        }
    }
    fn code(&self, d: String) -> String {d.chars().map(|x| {self.dict.get(&x).unwrap().clone()}).fold(String::new(), |x, y| {x + y.as_str()})}

    fn decode(&self, d: String) -> String {
        let mut res = String::new();
        let mut t = String::new();
        for i in d.chars() {
            t = t + i.to_string().as_str();
            match self.decode_dict.get(&t) {
                None => {}
                Some(a) => {
                    res += a.to_string().as_str()
                }
            }
        }
        res
    }

    fn show(&self) {
        self.dict.iter().for_each(|i| {println!("{} -> {}", i.0, i.1)});
    }
}

fn main() {
    let raw: Vec<u8> = "UNITED NATIONS, September 23. /TASS/. Hungarian Foreign Minister Peter Szijjarto commended his country’s cooperation with Russia’s energy giant Gazprom following a meeting with his Russian counterpart Sergey Lavrov on the sidelines of the 77th UN General Assembly in New York. We have a very comprehensive cooperation on the field of energy. For us, it is extremely important to ensure that the energy supply of the country is safe, Szijjarto told reporters after the talks. We would like to avoid a situation when any Hungarian household, family or company would be limited in using gas or oil products. Our cooperation with Gazprom has been going on in a very fair manner. Since September 1 we received the increased volume of gas deliveries on a daily basis, the minister continued. On top of the already contracted volume, we receive 5.8 million cubic meters of gas on the Turkish Stream pipeline. He described the Turkish Stream as basically, the only safe and reliable and predictable route for current gas supplies to Hungary. Today I expressed my appreciation both to Bulgaria and Serbia for ensuring the safe transit, and, of course, the Turkish colleagues as well, Szijjarto said. We hope that this cooperation with Gazprom will go on according to the contract we have signed.. Szijjarto said he planned to meet with Rosatom chief Alexey Likhachev in Vienna next week. We have received the final establishment permit for our new nuclear power plant, which we will construct based on the contract with Rosatom. I am going to meet with the CEO of Rosatom, Alexey Likhachev, on Monday in Vienna on the margins of the IAEA [International Atomic Energy Agency] congress, he told reporters. We will put together a schedule for the upcoming months and years, basically, in order to complete the project by 2030, he added. Currently, the Paks NPP, built according to the Soviet design, operates four power units with VVER-440 reactors. Located 100 km south of Budapest, the plant accounts for 49.6% of production and more than a third of electricity consumption in the republic. The construction of the second stage of the Paks nuclear power plant is expected to begin this year after the issuance of all necessary permits by the Hungarian Atomic Energy Agency. Two new VVER-1200 reactors should be launched by the end of this decade. The project, with an estimated cost of 12.5 billion euro, is supposed to be carried out by 80% at the expense of a Russian loan.".to_ascii_lowercase().chars().filter(|x| x.is_lowercase()).map(|x| x as u8).collect();
    let raw = String::from_utf8(raw).unwrap();
    let t = String::from(&raw);
    let mut h = HaffmanCoder::new(t);
    h.construct();
    println!("Input is :\n{}\n", &raw);
    h.show();
    println!();
    println!("Output is :\n{}", h.code(raw));
}
